package com.cn.codebrush.字符串;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Boolean
 * @Date 2022/6/21 11:25
 * @Version 1.0
 */
public class 剑指OfferII085生成匹配的括号 {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(8));
    }

    static List<String> list = new ArrayList<>();
    public static List<String> generateParenthesis(int n) {
        generateParenthesisHelper(n,n,"");
        return list;
    }

    public static void generateParenthesisHelper(int left,int right,String str) {
        if(left == 0 && right == 0){
            list.add(str);
        }
        if(left < 0){
            return;
        }
        if(right < left){
            return;
        }
        generateParenthesisHelper(left-1,right,str+"(");
        generateParenthesisHelper(left,right-1,str+")");
    }
}
